package com.cn.algorithm02.class23;


/***
 * @author: hels
 * @description: 样本对应模型
 * 给定3个参数，N，M，K
 * 怪兽有N滴血，等着英雄来砍自己
 * 英雄每一次打击，都会让怪兽流失[0~M]的血量
 * 到底流失多少?每一次在[0~M]上等概率的获得一个值
 * 求K次打击之后，英雄把怪兽砍死的概率
 **/
public class C01_KillMonster {
    /**
     * 暴力递归
     */
    public static double right1(int times, int M, int hp) {
        if (hp <= 0 || M <= 0 || times <= 0) {
            return 0;
        }
        long all = (long) Math.pow(M + 1, times);
        long kill = process(times, M, hp);
        return (double) kill / all;
    }

    private static long process(int times, int M, int hp) {
        if (times == 0) {
            return hp <= 0 ? 1 : 0;
        }
        if (hp <= 0) {
            return (long) Math.pow(M + 1, times);
        }

        long ways = 0;
        for (int i = 0; i <= M; i++) {
            ways += process(times - 1, M, hp - i);
        }
        return ways;
    }

    /**
     * 动态规划
     */
    public static double dp1(int times, int M, int hp) {
        if (times <= 0 || M <= 0 || hp <= 0) {
            return 0;
        }

        long[][] dp = new long[times + 1][hp + 1];
        dp[0][0] = 1;
        for (int time = 1; time <= times; time++) {
            dp[time][0] = (long) Math.pow(M + 1, time);
            for (int rest = 1; rest <= hp; rest++) {

                long ways = 0;
                for (int k = 0; k <= M; k++) {
                    if (rest - k >= 0) {
                        ways += dp[time - 1][rest - k];
                    } else {
                        ways += (long) Math.pow(M + 1, time - 1);
                    }
                }
                dp[time][rest] = ways;
            }
        }
        long all = (long) Math.pow(M + 1, times);
        long kill = dp[times][hp];
        return (double) kill / all;
    }

    /**
     * 2
     * 动态规划2
     */
    public static double dp2(int times, int M, int hp) {
        if (times <= 0 || M <= 0 || hp <= 0) {
            return 0;
        }

        long[][] dp = new long[times + 1][hp + 1];
        dp[0][0] = 1;
        for (int time = 1; time <= times; time++) {
            dp[time][0] = (long) Math.pow(M + 1, time);
            for (int rest = 1; rest <= hp; rest++) {
                dp[time][rest] += dp[time - 1][rest];
                dp[time][rest] += dp[time][rest - 1];

                if (rest - 1 - M >= 0) {
                    dp[time][rest] -= dp[time - 1][rest - 1 - M];
                } else {
                    // 此处逻辑概念中要减去多加的数值
                    //
                    dp[time][rest] -= (long) Math.pow(M + 1, time - 1);
                }
            }
        }
        long all = (long) Math.pow(M + 1, times);
        long kill = dp[times][hp];
        return (double) kill / all;
    }

    public static double dp3(int hp, int M, int times) {
        if (hp < 1 || M < 1 || times < 1) {
            return 0;
        }
        long all = (long) Math.pow(M + 1, times);
        long[][] dp = new long[times + 1][hp + 1];
        dp[0][0] = 1;
        for (int time = 1; time <= times; time++) {
            dp[time][0] = (long) Math.pow(M + 1, time);
            for (int rest = 1; rest <= hp; rest++) {
                dp[time][rest] = dp[time][rest - 1] + dp[time - 1][rest];
                if (rest - 1 - M >= 0) {
                    dp[time][rest] -= dp[time - 1][rest - 1 - M];
                } else {
                    dp[time][rest] -= Math.pow(M + 1, time - 1);
                }
            }
        }
        long kill = dp[times][hp];
        return (double) ((double) kill / (double) all);
    }

    public static void main(String[] args) {
//        int times = 3, M = 7, hp = 3;
        int maxTimes = 20;
        int maxM = 10;
        int maxHp = 15;
        int times = (int) (Math.random() * maxTimes) + 1;
        int M = (int) (Math.random() * maxM) + 1;
        int hp = (int) (Math.random() * maxHp) + 1;

        System.out.println("START");
        for (int i = 0; i < 100; i++) {
            System.out.print(i + " ");
            double r = right1(times, M, hp);
            double dp1 = dp1(times, M, hp);
            double dp2 = dp2(times, M, hp);
            double dp3 = dp3(hp, M, times);

            if (r != dp1) {
                System.out.println("o1ops");
            }
            if (r != dp2) {
                System.out.println("o2ops");
            }
            if (r != dp3) {
                System.out.println("o3ops");
            }
            if (r != dp1 || r != dp2 || r != dp3) {
                System.out.println(r);
                System.out.println(dp1);
                System.out.println(dp2);
                System.out.println(dp3);
            }

        }
        System.out.println(

        );
        System.out.println("END");


    }
}
